/*
day161_2
2020.2.5
*/
#include<vector>
//#include<iostream>
#include<cstdlib>
using namespace std;

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();
        int n=obstacleGrid[0].size();
        
        unsigned int **arr=(unsigned int **) malloc(m*sizeof(unsigned int *));
        for(int i=0;i<m;i++)
        {
        	arr[i]=(unsigned int *) malloc(n*sizeof(unsigned int));
		}
		
		arr[0][0]=(obstacleGrid[0][0]==1 ? 0 : 1);
		for(int i=1;i<m;i++)
		{
			arr[i][0]=(obstacleGrid[i][0]==1 || arr[i-1][0]==0) ? 0 : 1 ;
		}
		for(int i=1;i<n;i++)
		{
			arr[0][i]=(obstacleGrid[0][i]==1 || arr[0][i-1]==0) ? 0 : 1 ;
		}
		
		for(int i=1;i<m;i++)
		{
			for(int j=1;j<n;j++)
			{
				arr[i][j]=(obstacleGrid[i][j]==1) ? 0 : arr[i-1][j]+arr[i][j-1];
			}
		}
		
		return arr[m-1][n-1];
    }
};

int main()
{
	return 0;
}
